package JZOffer;

import com.sun.org.apache.bcel.internal.generic.RETURN;

import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * 剑指 Offer 40. 最小的k个数
 * 输入整数数组 arr ，找出其中最小的 k 个数。
 * 例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。
 * **/

//利用最小堆
class Solution40_1 {
    public int[] getLeastNumbers(int[] arr, int k) {
        //最小堆
        Queue<Integer> queue = new PriorityQueue<>((o1,o2)->(o2.compareTo(o1)));

        for (int i:arr){
            queue.add(i);
            while (!queue.isEmpty() && queue.size() > k) queue.remove();
        }
        int[] res = new int[k];
        for (int i = 0; i < k; i++){
            res[i] = queue.poll();
        }
        return res;
    }
}

//二分+快排partition
//左边比arr[k-1]的值小，右边比arr[k-1]的值大
class Solution40_2 {
    public int[] getLeastNumbers(int[] arr, int k){
        if (arr == null || arr.length == 0) return new int[0];
        int lo = 0, hi = arr.length - 1;

        while (lo < hi){
            int index = partition(arr, lo ,hi);
            //二分
            if (index == k - 1) break;
            //index < k - 1:相当于想要80分，只得60分，只需在61分以上寻找
            else if (index < k - 1) lo = index + 1;
            else hi = index - 1;
        }
        //返回arr数组中0~k-1，k个数
        return Arrays.copyOfRange(arr, 0, k);
    }
    //partition函数
    public int partition(int arr[], int lo, int hi){
        int index = lo;//index设为第一个位置
        int pivot = arr[lo];//存放第一个位置的value

        for (int i = lo; i <= hi; i++){
            if (arr[i] < pivot) swap(arr, i, ++index);
        }
        swap(arr, lo, index);
        return index;
    }

    public void swap(int[] arr, int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

//对原数组从小到大排序后取出前 k 个数即可。
class Solution40_3 {
    public int[] getLeastNumbers(int[] arr, int k){
        int[] vec = new int[k];
        Arrays.sort(arr);
        for (int i = 0; i < k; i++) {
            vec[i] = arr[i];
        }
        return vec;
    }
}